/*
 * @lc app=leetcode.cn id=1606 lang=cpp
 *
 * [1606] 找到处理最多请求的服务器
 */
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <stdlib>
#include <string>
#include <string.h>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <cmath>

using namespace std;
// @lc code=start
class Solution {
public:
    vector<int> busiestServers(int k, vector<int>& arrival, vector<int>& load) {
         // O（nlog（n））才能通过
        vector<int> count(k, 0); //记录服务了多少个请求
        int now = 0; // 公共时间，理解为“现在”
        int size = arrival.size();
        // 小顶堆记录最早释放的服务器的时间与其编号
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > busy; 
        //set里存放当前可以工作的机器
        set<int> free;
        //初始化，所有机器都可以工作
        for (int i = 0; i < k; ++i) {
            free.insert(i);
        } 
        for (int i = 0; i < size; ++i){
            now = arrival[i]; //时间在变化
            while (!busy.empty() && busy.top().first <= now){ //存放可以工作的机器
                free.insert(busy.top().second);
                busy.pop();
            }
            
            if (free.empty()) {
                continue; //没有空闲 跳过
            } 
            //二分查找，寻找下界
            auto temp = free.lower_bound(i % k);
            if (temp == free.end()) {
                temp = free.lower_bound(0);
            } 
            busy.push(make_pair(now + load[i], *temp));
            count[*temp] ++;
            free.erase(temp);
        }

        int max_times = *max_element(count.begin(), count.end());
        vector<int> res;
        for (int i = 0; i < k; ++i){
            if (count[i] == max_times) {
                res.emplace_back(i)；
            } 
        }
        return res;
    }
};
// @lc code=end

//没有使用优先队列会超时
// vector<int> ret;
// vector<int> deal(k);
// vector<int> server(k,0);
// int n = arrival.size();
// int m = 0;
// for(int i = 0;i < n;i++) {
//     int count = k;
//     int j = i % k;
//     while(count) {
//         if(arrival[i] >= server[j]) {
//             server[j] = arrival[i] + load[i];
//             deal[j]++;
//             if(m == deal[j]) {
//                 ret.push_back(j);
//             }else {
//                 m = max(deal[j],m);
//                 ret.clear();
//                 ret.push_back(j);
//             }
            
//             break;
//         }else {
//             j = ++j % k;
//             count--;
//         }
//     }
// }
// return ret;